Embodiments of the present invention relate to prefetching data from a memory. In particular, the present invention relates to methods and apparatus for prefetching data from a memory for use by a processor.
Instructions executed by a processor often use data that may be stored in a memory device such as a Random Access Memory (RAM). For example, a processor may execute a LOAD instruction to load a register with data that is stored at a particular memory address. In many systems, because the access time for the system memory is relatively slow, frequently used data elements are copied from the system memory into a faster memory device called a cache and, if possible, the processor uses the copy of the data element in the cache when it needs to access (i.e., read to or write from) that data element. If the memory location that is accessed by an instruction has not been copied into a cache, then the access to the memory location by the instruction is said to cause a xe2x80x9ccache missxe2x80x9d because the data needed could not be obtained from the cache. Computer systems operate more efficiently if the number of cache misses is minimized.
One way to decrease the time spent waiting to access a RAM is to xe2x80x9cprefetchxe2x80x9d data from the RAM memory before it is needed and, thus, before the cache miss occurs. Many processors have an instruction cycle in which instructions to be executed are obtained from memory in one step (i.e., an instruction fetch) and executed in another step. If the instruction to be executed accesses a memory location (e.g., a memory LOAD), then the data at that location must be fetched into the appropriate section of the processor from a cache or, if a cache miss, from a system memory. A cache prefetcher attempts to anticipate which data addresses will be accessed by instructions in the future and prefetches the data to be accessed from the memory before the data is needed. This prefetched data may be stored in a cache or buffer for later use.
Prior prefetching schemes determine a xe2x80x9cstridexe2x80x9d for memory instructions such as LOAD""s and then prefetch data using this stride. The stride for an instruction in a program may be defined as the distance between the memory addresses loaded by two consecutive executions of the instruction. As used herein, xe2x80x9cinstructionxe2x80x9d refers to a particular instance of an instruction in the program, with each instruction being identified by a different instruction pointer (xe2x80x9cIPxe2x80x9d) value. Stride based prefetch schemes are premised on the theory that an instruction will access a series of memory locations that are the same distance apart from one another. This prediction is often accurate if, for example, the program is in a loop or nested loop or is stepping though a table.